10098. Быстрая генерация отсортированных перестановок

По заданной строке вывести все перестановки ее символов в лексикографическом порядке.

Вход. Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит n символов (n £ 10).

Выход. Для каждой входной строки вывести все перестановки в лексикографическом порядке начиная с наименьшей. Каждую перестановку выводить в отдельной строке. После вывода всех перестановок для каждого теста печатать пустую строку.

Пример входа

3
ab
abc
bca

Пример выхода

ab

ba

abc

acb

bac

bca

cab

cba

abc

acb

bac

bca

cab

cba

РЕШЕНИЕ

комбинаторика, генерация перестановок

Анализ алгоритма

Сортируем символы входной строки по возрастанию. Далее используем встроенную функцию next_permutation для генерации всех перестановок.

Пример

Для строки bca (3 тест) наименьшей перестановкой будет abc, а наибольшей cba.

Реализация алгоритма

Для каждого теста читаем входную строку, вычисляем ее длину и сортируем символы в лексикографическом порядке.

scanf("%s", &s);len = strlen(s);

sort(s,s+len);

Выводим текущую перестановку символов (строку s) и генерируем следующую перестановку пока это возможно.

do {

printf("%s\n",s);

} while(next_permutation(s,s+len));

printf("\n");